import java.util.*;

public class question_40 {
}
class Solution_40 {
    //    思路是采用dfs的方法
    public void dfs(List<List<Integer>> final_result,int arr[],int target,HashMap<String,List<Integer>> result,int[] temp,int index,int start){
//        相比于39题这里要多添加一个break的条件，因为40题的candidate里的数字是不能重复使用的，所以
//        可能出现吧candidate所有的值加起来都不够target的情况，所以这里要判断一下
        if(start==arr.length){
            return;
        }
//        进来之前先把temp数组在index前面的数值全部加一遍
        int sum=0;
        for (int i = 0; i < index; i++) {
            sum+=temp[i];
        }
        for (int i = start; i < arr.length; i++) {
            if(sum+arr[i]==target){
                List<Integer> list=new ArrayList<>();
                temp[index]=arr[i];
                String key="";
                for (int j = 0; j <= index; j++) {
                    list.add(temp[j]);
                    key=key+temp[j]+"#";
                }
                if(result.get(key)==null){
                    result.put(key,list);
                    final_result.add(list);
                }
//                这个时候说明已经是等于了，那么就不再需要往下递归和往右边遍历了，因为往右边只会变得更大，因为是有序数组来的
                return;
            } else if (sum+arr[i]>target) {
//                这个时候说明已经是大于了，那么就不再需要往下递归和往右边遍历了，因为往右边只会变得更大，因为是有序数组来的
                return;
            }else {
//                小于，还得接着递归
                temp[index]=arr[i];
//                这里是细节，39题里面数字可重复，所以往下递归的时候位置还是i,但是这题不行了，所以只能往后走了
//                dfs(arr,target,result,temp,index+1,i);
                dfs(final_result,arr,target,result,temp,index+1,i+1);
            }
        }
        return;

    }
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
//      定义一个hashmap用来去重
//        比如{1,1,2,5}，则对应的key就是“1#1#2#5#”，value就是{1,1,2,5}
        HashMap<String,List<Integer>> hashMap=new HashMap<>();
        //        默认是从小到大排序的
        Arrays.sort(candidates);
        int len=candidates.length;
        int temp[]=new int[len];
        List<List<Integer>> result = new ArrayList<>();
        dfs(result,candidates,target,hashMap,temp,0,0);
        return result;
    }
}
